#define DEBUG
#include <cstdio>
#include <cstring>

using namespace std;

typedef long long ll;

const int mods=1000000007;

class Matrix {
public:
  int n, m;
  ll f[2][2];

  void one(int t) {
    n = m = t;
    memset(f, 0, sizeof f);
    for (int i=0; i<n; i++) {
      f[i][i] = 1;
    }
  }

  void mul(Matrix &a, Matrix &b) {
    n = a.n, m = b.m;
    for (int i=0; i<n; i++) {
      for (int j=0; j<m; j++) {
        f[i][j] = 0;
        for (int k=0; k<a.m; k++) {
          f[i][j] = (a.f[i][k]*b.f[k][j]%mods+f[i][j])%mods;
        }
      }
    }
  }

  void qpower(Matrix &x, int t) {
    if (!t) {
      one(x.n);
      return ;
    }
    static Matrix a[2], s[2];
    int i=0, j=0;
    a[i] = x, s[j].one(x.n);
    for (; t>1; t>>=1) {
      if (t&1) {
        j = !j;
        s[j].mul(a[i], s[!j]);
      }
      i = !i;
      a[i].mul(a[!i], a[!i]);
    }
    mul(a[i], s[j]);
  }
};

int calcPhi(int x) {
  int ret = x;
  for (int i=2; i*i<=x; i++) {
    if (x%i==0) {
      ret = ret/i*(i-1);
    }
    for (; x%i==0; x/=i);
  }
  if (x>1) {
    ret = ret/x*(x-1);
  }
  return ret;
}

ll qpower(ll a, int n) {
  ll s=1;
  for (; n>1; n>>=1) {
    if (n&1) {
      s = s*a%mods;
    }
    a = a*a%mods;
  }
  return s*a%mods;
}

ll calc(int n, int t, int k) {
  static Matrix x;
  x.n = x.m = 2;
  x.f[0][0] = 1, x.f[0][1] = k, x.f[1][0] = 1, x.f[1][1] = 0;
  x.qpower(x, t-1);
  ll temp=(x.f[0][1]+x.f[0][0]+x.f[1][0]*k%mods)%mods;

  return temp*calcPhi(n/t)%mods;
}

int main() {
  freopen("bracelet.in", "r", stdin);
  freopen("bracelet.out", "w", stdout);

  int n, k;
  scanf("%d %d", &n, &k);

  ll ans=0;
  for (int t=1; t*t<=n; t++) {
    if (n%t==0) {
      ans = (calc(n, t, k)+ans)%mods;
      if (t*t!=n) {
        ans = (calc(n, n/t, k)+ans)%mods;
      }
    }
  }
  printf("%lld", ans*qpower(n, mods-2)%mods);

  fclose(stdin);
  fclose(stdout);
  return 0;
}
